
#ifndef TOKZRGENTR_UTILS_AUTOMATICS_H
#define TOKZRGENTR_UTILS_AUTOMATICS_H
#include"ucs2_ranges.h"
#include"asserts.h"
#include"char_set_table.h"
#include<memory>
#include<vector>
#include<map>
//#	Declares Finite Automatics.
//#	e.g.	nfa and dfa for this project
namespace TokzrGentr
{
	class nfa_transition;
	class nfa_status;
	class nfa_allocator;
	class nfa_cstr;
	
	struct nfa;
	struct temp_nfa;

	struct temp_nfa
	{
		nfa_status *_start;
		nfa_status *_finish;
	};
	struct nfa
	{
	public:
		friend class nfa_cstr;
		friend class nfa_alloc;
	private:
		nfa_status *_start;
		nfa_status *_finish;
		unsigned _mark;
	public:
		nfa(nfa_status *start, nfa_status *finish,unsigned m)
			:_start(start), _finish(finish),_mark(m) {}
		nfa_status *start() const { return _start; }
		nfa_status *finish() const { return _finish; }
		unsigned mark() { return _mark; }
	};
	
	//#	transtion for nfa.
	class nfa_transition
	{
	public:
		friend class nfa_cstr;
		friend class nfa_alloc;
	private:
		nfa_status *_to;
		std::shared_ptr<ucs2_ranges_set> _char_sets_ptr;
	public:
		nfa_transition()
			:_to(nullptr) {}
		nfa_status *to(){ return _to; }
		std::shared_ptr<ucs2_ranges_set> content_ptr()  
		{
			return _char_sets_ptr; 
		}
	};

	//# status for nfa.
	class nfa_status
	{
	public:
		using trans_type = nfa_transition;
		using iterator = trans_type**;

		friend class nfa_cstr;
		friend class nfa_alloc;
		friend class dfa_cstr;
	private:
		size_t _trans_num;
		nfa_transition*_trans[2];
		bool _is_accepted;
	public:
		nfa_status()
			:_trans_num(0), _trans{ nullptr,nullptr }, _is_accepted(false){}
		//#	for_each
		//# e.g. using for(auto trans:nfa_status) to traverse the trans inside the nfa_status
		iterator begin() { return _trans; }
		iterator end() { return _trans + _trans_num; };
	};


	//# Using the static function of this class to alloc
	//#	the memory of nfa_likes data.
	//#	It manage memory pool to accelerate the alloc's speed;
	class nfa_alloc
	{
	private:
		union status_block
		{
			char data[sizeof(nfa_status)];
			status_block *free_list_link;
		};

		union transition_block
		{
			char data[sizeof(nfa_transition)];
			transition_block *free_list_link;
		};

		static union status_block *free_status_list;
		static union transition_block *free_transition_list;
	public:
		static nfa_status *alloc_status()
		{
			nfa_status *status;
			if (free_status_list)
			{
				status_block *mem_block = free_status_list;
				free_status_list = free_status_list->free_list_link;
				status = new(mem_block->data) nfa_status;
			}
			else
			{
				status = new nfa_status();
			}
			return status;
		}
		static void free(nfa_status *status)
		{
			status_block *block = (status_block*)status;
			if (block)
			{
				block->free_list_link = free_status_list;
				free_status_list = block;
			}
		}
		static nfa_transition* alloc_transition()
		{
			nfa_transition *transition;
			if (free_transition_list)
			{
				transition_block *mem_block = free_transition_list;
				free_transition_list = free_transition_list->free_list_link;
				transition = new(mem_block->data) nfa_transition;
			}
			else
			{
				transition = new nfa_transition;
			}
			return transition;
		}
		static void free(nfa_transition *trans)
		{
			if (trans)
			{
				//#For smart pointer to destroy,this statement is neccessary.
				trans->~nfa_transition();
				transition_block *block = (transition_block*)trans;
				block->free_list_link = free_transition_list;
				free_transition_list = block;
			}
		}

		//#	return all the memory blocks in the memory pool.
		//# give them back to the system.
		static void clean_pool()  
		{
			while (free_status_list)
			{
				auto status_ptr = (nfa_status*)free_status_list->data;
				free_status_list = free_status_list->free_list_link;
				delete status_ptr;
			}

			while (free_transition_list)
			{
				auto trans_ptr = (nfa_transition*)free_transition_list->data;
				free_transition_list = free_transition_list->free_list_link;
				delete trans_ptr;
			}
		}

		//#	breakdown the nfa automatically. 
		//#	free statuses and transitions attached it.
		static void free(nfa target)
		{
			//# while traverse the nfa
			//#	using the _is_accepted flag to mark whether the
			//# status has been traversed or not
			target._finish->_is_accepted = false;
			std::vector<nfa_status*> all_status;
			std::vector<nfa_status*> status_waiting = { target._start };
			while (!status_waiting.empty())
			{
				auto status = status_waiting.back();
				status_waiting.pop_back();
				if (status->_is_accepted)
					continue;
				status->_is_accepted = true;
				all_status.push_back(status);
				for (auto trans : *status)
				{
					status_waiting.push_back(const_cast<nfa_status*>(trans->_to));
				}
			}

			//free the nfa
			for (auto status : all_status)
			{
				for (auto trans : *status)
				{
					free(trans);
				}
				free(status);
			}
		}
	};
	union nfa_alloc::status_block *nfa_alloc::free_status_list = nullptr;
	union nfa_alloc::transition_block *nfa_alloc::free_transition_list = nullptr;

	//#	Using this class to construct a nfa
	//#	No right for the user to change the nfa_likes data.
	class nfa_cstr
	{
	public:
		static nfa_transition* epsilon_combine(nfa_status *from, nfa_status *to)
		{
			return char_set_combine(from, to, std::shared_ptr<ucs2_ranges_set>(nullptr));
		}
		static nfa_transition* char_set_combine(nfa_status *from, nfa_status *to, std::shared_ptr<ucs2_ranges_set> char_set_ptr)
		{
			ASSERT(from->_trans_num < 2);
			auto trans = nfa_alloc::alloc_transition();
			trans->_to = to;
			trans->_char_sets_ptr = char_set_ptr;
			from->_trans[from->_trans_num] = trans;
			from->_trans_num++;
			return trans;
		}
		inline static bool is_epsilon_transition(nfa_transition *trans)
		{
			return trans->_char_sets_ptr.get() == nullptr;
		}
		static nfa build_nfa(temp_nfa t_nfa,unsigned mark)
		{
			t_nfa._finish->_is_accepted = true;
			return { t_nfa._start,t_nfa._finish,mark };
		}
	};


	class dfa_transition;
	class dfa_status;
	class dfa_alloc;
	class dfa_cstr;
	class dfa;

	class dfa
	{
	public:
		friend class dfa_alloc;
		friend class dfa_cstr;
	private:
		dfa_status *_start;
	public:
		dfa(dfa_status*start)
			:_start(start) {}
		dfa_status *start() const
		{
			return _start;
		}
		friend bool operator<(const dfa &lhs, const dfa &rhs)
		{
			return std::less<decltype(lhs._start)>()(lhs.start(), rhs.start());
		}
	};

	class dfa_transition
	{
	public:
		using value_type = typename char_sets_table::value_type;
		friend class dfa_cstr;
		friend class dfa_alloc;
	private:
		value_type _val;
		dfa_status *_to;
	public:
		dfa_transition()
			:_val(0), _to(nullptr) {}
		value_type value() const 
		{
			return _val;
		}
		dfa_status* to()  const
		{
			return _to;
		}
	};

	class dfa_status
	{
	public:
		friend class dfa_alloc;
		friend class dfa_cstr;
		using iterator = std::vector<dfa_transition*>::iterator;
	private:
		std::vector<dfa_transition*> _trans;
		bool _is_accepted;
	public:
		unsigned _mark;
	public:
		dfa_status()
			:_is_accepted(false), _trans{},_mark(0) {}
		iterator begin() 
		{
			return _trans.begin();
		}
		iterator end()
		{
			return _trans.end();
		}
		bool is_accepted() { return _is_accepted; };
		unsigned mark() { return _mark; };
	};


	class dfa_alloc
	{

	public:
		union status_block
		{
			char data[sizeof(dfa_status)];
			status_block *free_list_link;
		};
		union transition_block
		{
			char data[sizeof(dfa_transition)];
			transition_block *free_list_link;
		};
	private:
		static status_block* free_status_list;
		static transition_block*free_transition_list;
	public:
		static dfa_transition *alloc_transition()
		{
			if (free_transition_list)
			{
				auto block = free_transition_list;
				free_transition_list = free_transition_list->free_list_link;
				return new(block->data) dfa_transition();
			}
			else
			{
				return new dfa_transition();
			}
		}
		static dfa_status *alloc_status(bool is_accepted = false)
		{
			dfa_status *status;
			if (free_status_list)
			{
				auto block = free_status_list;
				free_status_list = free_status_list->free_list_link;
				status = new(block->data)dfa_status;
			}
			else
			{
				status = new dfa_status;
			}
			status->_is_accepted = is_accepted;
			return status;
		}
		static void free(dfa_transition *trans)
		{
			if (trans)
			{
				auto block = (transition_block*)(trans);
				block->free_list_link = free_transition_list;
				free_transition_list = block;
			}
		}
		static void free(dfa_status *status)
		{
			if (status)
			{
				auto block = (status_block*)(status);
				block->free_list_link = free_status_list;
				free_status_list = block;
			}
		}
		//#	Free the dfa automatically.
		static void free(dfa target)
		{
			std::set<dfa_status *> traversed;
			std::vector<dfa_status *> waiting;
			waiting.push_back(target._start);
			while (!waiting.empty()) {
				auto s = waiting.back();
				waiting.pop_back();
				if (traversed.find(s) != traversed.end())
					continue;
				traversed.insert(s);
				for (auto trans : *s)
					waiting.push_back(trans->to());
			}
			for (auto status : traversed)
			{
				for (auto trans : *status)
					dfa_alloc::free(trans);
				dfa_alloc::free(status);
			}
		}
	};

	class dfa_cstr
	{
	public:
		static dfa subset_construct(nfa nfa_target, char_sets_table *constructed_table)
		{
			//#	step1:remove the epsilon inside the nfa
			//# Mark the important status
			std::map<nfa_status*, dfa_status*> important_status;
			std::vector<nfa_status*> status_waiting_traverse;

			important_status.insert({ nfa_target.start(),dfa_alloc::alloc_status() });
			
			status_waiting_traverse.push_back(nfa_target.start());

			while (!status_waiting_traverse.empty())
			{
				auto status = status_waiting_traverse.back();
				status_waiting_traverse.pop_back();
				if (status->_is_accepted)
					continue;
				status->_is_accepted = true;
				for (auto trans : *status)
				{
					if (!nfa_cstr::is_epsilon_transition(trans))
					{
						important_status.insert({ trans->to(),dfa_alloc::alloc_status(trans->to() == nfa_target.finish()) });
					}
					status_waiting_traverse.push_back(trans->to());
				}
			}
			//#	remove the epsilon transition and translate to char_set_table's mapping value
			std::vector<nfa_transition*> trans_will_attach;
			std::set<nfa_status*> n_status_traversed;
			for (auto n2dpair : important_status)
			{
				//#	Find the non-epsilon nfa_transitions that will attach
				status_waiting_traverse.push_back(n2dpair.first);
				n_status_traversed.clear();
				trans_will_attach.clear();
				bool is_accepted = n2dpair.second->_is_accepted;
				while (!status_waiting_traverse.empty())
				{
					auto status = status_waiting_traverse.back();
					status_waiting_traverse.pop_back();
					if (n_status_traversed.find(status) != n_status_traversed.end())
						continue;
					n_status_traversed.insert(status);
					for (auto trans : *status)
					{
						if (!nfa_cstr::is_epsilon_transition(trans))
							trans_will_attach.push_back(trans);
						else {
							status_waiting_traverse.push_back(trans->to());
							is_accepted = is_accepted || (trans->to() == nfa_target.finish());
						}
					}
				}
				auto d_status = n2dpair.second;
				d_status->_is_accepted = is_accepted;
				if (d_status->is_accepted())
					d_status->_mark = nfa_target.mark();
				//#	traslate mapping value
				for (auto trans : trans_will_attach)
				{
					auto dest = important_status[trans->to()];
					auto val_set = constructed_table->get(trans->content_ptr());
					for (auto val : val_set)
						dfa_cstr::combine(d_status, dest, val);
				}
			}

			//#	step2:subset construct algorithm
			auto d_start = important_status[nfa_target.start()];

			dfa dfa_target = subset_construct(dfa(d_start),constructed_table);

			dfa_alloc::free(dfa(d_start));
			return dfa_target;
		}
		static dfa subset_construct(std::set<dfa> dfas, char_sets_table *constrcuted_table)
		{
			std::set<dfa_status*> initialized_set;
			bool is_accepted = false;
			unsigned initialized_mark = 0;
			for (auto p : dfas)
			{
				initialized_set.insert(p.start());
				is_accepted = is_accepted || p.start()->is_accepted();
				if (initialized_mark < p.start()->mark())
					initialized_mark = p.start()->mark();
			}
			std::map<std::set<dfa_status*>, dfa_status*> dfa_sets;
			auto initialized_status = dfa_alloc::alloc_status(is_accepted);
			initialized_status->_mark = initialized_mark;
			dfa_sets.insert({initialized_set,initialized_status });
			std::set<dfa_status*> dstatus_traversed;
			std::vector<std::set<dfa_status*>> dstates_waiting = {initialized_set};
			while (!dstates_waiting.empty())
			{
				auto sets = dstates_waiting.back();
				dstates_waiting.pop_back();
				auto status = dfa_sets[sets];
				if (dstatus_traversed.find(status) != dstatus_traversed.end())
					continue;
				dstatus_traversed.insert(status);
				std::map<char_sets_table::value_type, std::pair<std::set<dfa_status*>, unsigned>> current_map;
				
				for (auto status : sets)
					for (auto trans : *status)
					{
						decltype(current_map)::iterator p;
						if ((p = current_map.find(trans->value())) == current_map.end())
						{
							current_map.insert({ trans->value(),
							{ { trans->to() },trans->to()->mark() }
							});
						}
						else
						{
							p->second.first.insert({ trans->to() });
							if (p->second.second < trans->to()->mark())
								p->second.second = trans->to()->mark();
						}
					}

				for (auto p : current_map)
				{
					auto val = p.first;
					auto sets = p.second.first;
					auto p_iter = dfa_sets.find(sets);
					if (p_iter != dfa_sets.end())
					{
						dfa_cstr::combine(status, p_iter->second, val);
					}
					else
					{
						auto d_status = dfa_alloc::alloc_status((p.second.second != 0));
						d_status->_mark = p.second.second;
						dfa_sets.insert({ sets,d_status });
						dfa_cstr::combine(status, d_status, val);
					}
					dstates_waiting.push_back(sets);
				}
			}
			dfa target(dfa_sets[initialized_set]);
			return target;
		}
		static dfa subset_construct(dfa dfa_target, char_sets_table *constructed_table)
		{
			std::set<dfa> single_one;
			single_one.insert(dfa_target);
			return subset_construct(single_one, constructed_table);
		}
		static dfa_transition *combine(dfa_status *from, dfa_status*to, typename dfa_transition::value_type val)
		{
			auto trans = dfa_alloc::alloc_transition();
			trans->_val = val;
			trans->_to = to;
			from->_trans.push_back(trans);
			return trans;
		}
	};

	dfa_alloc::status_block* dfa_alloc::free_status_list = nullptr;
	dfa_alloc::transition_block * dfa_alloc::free_transition_list = nullptr;

}

#endif // !TOKZRGENTR_UTILS_AUTOMATICS_H
